<?php
/** 
 * 题目：链表中倒数第k个结点
 * 解析：两个指针，先让第一个指针和第二个指针都指向头结点，然后再让第一个指正走(k-1)步，到达第k个节点。然后两个指针同时往后移动，当第一个结点到达末尾的时候，第二个结点所在位置就是倒数第k个节点了
 * 
 */

class ListNode
{
    public $val;
    public $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}

function FindKthToTail($head, $k)
{
    $pre = $head;
    $last = $head;
    $step = 0;
    while ($last->next) {
    	if ($step >= $k - 1) {
    		$pre = $pre->next;
    	} 
    	$last = $last->next;
    	$step++;
    }
    return $pre;
}

$node = new ListNode(1);
$node->next = new ListNode(2);
$node->next->next = new ListNode(3);
$node->next->next->next = new ListNode(4);
$node->next->next->next->next = new ListNode(5);
$node->next->next->next->next->next = new ListNode(6);

$retNode = FindKthToTail(null, 2);
if ($retNode==null) {
	echo "node is null";
} else {
	echo $retNode->val;
}


